package org.example.leetCode;

import java.util.*;

/**
 * @Author Qinkai
 * @Description TODO $
 * @Date $ 2021-09-15$
 * @Param $
 * @return $
 **/
public class ThreeSum {

    public static void main(String[] args) {
        int[] ints = {-1, 0, 1, 2, -1, -4};
        ThreeSum threeSum = new ThreeSum();
        List<List<Integer>> lists = threeSum.threeSum(ints);
    }


    public List<List<Integer>> threeSum(int[] nums) {
        if (nums.length < 3) {
            return new ArrayList<>();
        }
        List<List<Integer>> res = new ArrayList<>();
        int[] sort = Arrays.stream(nums).sorted().toArray();

        for (int i = 0;sort[i] < 0 && i < sort.length-2; i++) {
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int j = i + 1; j < sort.length; j++) {
                int sum = -sort[i];
                if (map.containsKey(sort[j])) {
                    map.put(sort[j], sum - sort[j]);
                } else {
                    map.put(sum - sort[j], null);
                }
            }
            Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
            for (Map.Entry<Integer, Integer> entry : entries) {
                if (entry.getValue() != null) {
                    res.add(Arrays.asList(sort[i], entry.getKey(), entry.getValue()));
                }
            }

        }
        return res;
    }
}
